# 给定一个没有重复数字的序列，返回其所有可能的全排列。

# 示例:

# 输入: [1,2,3]
# 输出:
# [
# [1,2,3],
# [1,3,2],
# [2,1,3],
# [2,3,1],
# [3,1,2],
# [3,2,1]
# ]

# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/permutations
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import List


class Solution:
    def __init__(self):
        self.res = []
    def permute(self, nums: List[int]) -> List[List[int]]:
        """自己的回溯算法
        """
        if not nums:
            return []
        self.find(nums, [])
        return self.res

    def find(self, nums, l):
        """剩余的数，　已有的数
        """
        if not nums:
            self.res.append(l)
            return
        for i in range(len(nums)):
            tmp = nums.copy()
            tmp.remove(nums[i])

            if l:
                p = [*l, nums[i]]
            else:
                p = [nums[i]]
            self.find(tmp,  p)

class Solution2:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(nums, tmp):
            if not nums:
                res.append(tmp)
                return 
            for i in range(len(nums)):
                backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
        backtrack(nums, [])
        return res

class Solution:
    """看视频，讲师的例子
    """
    def __init__(self):
        self.res = []
        self.used = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.used = [False] * len(nums)
        self.generatePermutation(nums, 0, [])
        return self.res

    def generatePermutation(self, nums, index, p):
        if index == len(nums):
            self.res.append(p)

        for i in range(len(nums)):
            if not self.used[i]:
                # p.append(nums[i]
                self.used[i] = True
                self.generatePermutation(nums, index + 1, p+[nums[i]])
                self.used[i] = False






if __name__ == "__main__":
    print(Solution().permute([1,2,3]))

def test1():
    assert Solution().permute([1, 2, 3]) == [
        [1, 2, 3],
        [1, 3, 2],
        [2, 1, 3],
        [2, 3, 1],
        [3, 1, 2],
        [3, 2, 1]
    ]

def test_time():
    Solution().permute([1,2,3,4,5,6,7,8,9,0])
    assert 1==1

# def test_empty():
    # assert Solution().permute([]) == []
